package everydayone.sortArray;
/**
 * @Date 2020/03/31
 * @author 王光浩
 * @Thinking 使用快速排序
 * @Analysis 时间复杂度O（nlogn），空间复杂度O（logn），最坏是O（n^2）
 */
public class MyMethodTwo {
	 public int[] sortArray(int[] nums) {
		 quick_sort(nums,0,nums.length-1);
		 return nums;
	 }
	 //快速排序
	 private void quick_sort(int[] nums,int left,int right) {
		 if(left>=right)return;
		 int le=left;
		 int ri=right;
		 int basic=nums[left];
		 while(le<ri) {
			 //从右向左找出第一个比basic小的数字，并进行交换
			 while(le<ri && nums[ri]>=basic) {
				 ri--;
			 }
			 nums[le]=nums[ri];
			 //从左向右找第一个比basic大的数字
			 while(le<ri && nums[le]<=basic)
				 le++;
			 nums[ri]=nums[le];
		 }
		 //最后将所有比basic小的数存放在basic的左边，将比basic大的数字存放在basic的右边
		 nums[le]=basic;
		 quick_sort(nums,left,le-1);
		 quick_sort(nums,le+1,right);
	 }
}
